package com.wfm.leetcode.editor.cn;

import com.wfm.common.TreeNode;
import java.util.HashMap;

/**
 * 递归法：
 * 前序： 根【左节点】【右节点】
 * 中序：【左节点】根【右节点】
 * 这题难就难在下标定位部分
 * 3 9 20 15 7   9 3 15 20 7
 * pl        pr  il        ir
 * root_idx = in.get(pl)
 * 左子树长度：root_idx-il
 *            前序遍历区间                中序遍历区间
 * 左子树：[pl+1,pl+1+(root_idx-il)-1]  [il,root_idx-1]
 * 右子树：[pl+1+(root_idx-il)-1+1,pr]   [root_idx+1,ir]
 *
 *
 * 0 1 2 3 4  长度5
 * i=0     j=4
 * j-i+1=5
 * i+5-1=j
 */
public class POne05从前序与中序遍历序列构造二叉树{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    HashMap<Integer,Integer> m = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            m.put(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    public TreeNode myBuildTree(int[] preorder, int[] inorder,int pl,int pr,int il,int ir) {
        if(pl>pr) return null;
        int root_idx = m.get(preorder[pl]);
        TreeNode root = new TreeNode(preorder[pl]);
        TreeNode left = myBuildTree(preorder, inorder, pl + 1, pl + 1 + root_idx - il - 1, il, root_idx - 1);
        TreeNode right = myBuildTree(preorder, inorder, pl + 1 + root_idx - il - 1 + 1, pr, root_idx + 1, ir);
        root.left=left;
        root.right=right;
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new POne05从前序与中序遍历序列构造二叉树().new Solution();
    }
}